package com.hdu.point_offer;


import java.util.Deque;
import java.util.LinkedList;

public class lcr184 {
    class Checkout {

        Deque<Integer> q1 = new LinkedList<>();
        Deque<Integer> max_q = new LinkedList<>();

        public Checkout() {

        }

        public int get_max() {
            if (max_q.isEmpty()) return -1;
            return max_q.peek();
        }

        public void add(int value) {
            q1.addLast(value);
            while (!max_q.isEmpty() && max_q.peekLast() < value)
            {
                max_q.pollLast();
            }
            max_q.addLast(value);
        }

        public int remove() {
            if (q1.isEmpty()) return -1;
            int delV = q1.pollFirst();
            if (delV == max_q.peek()) max_q.pollFirst();
            return delV;
        }
    }

/**
 * Your Checkout object will be instantiated and called as such:
 * Checkout obj = new Checkout();
 * int param_1 = obj.get_max();
 * obj.add(value);
 * int param_3 = obj.remove();
 */

/**
 * Your Checkout object will be instantiated and called as such:
 * Checkout obj = new Checkout();
 * int param_1 = obj.get_max();
 * obj.add(value);
 * int param_3 = obj.remove();
 */
}
